package com.future;

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

/**
 * Description:
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * <p>
 * k 是一个正整数，它的值小于或等于链表的长度。
 * <p>
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * <p>
 * 进阶：
 * <p>
 * 你可以设计一个只使用常数额外空间的算法来解决此问题吗？
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author weiruibai.vendor
 * Date: 2022/2/25 11:14
 */
public class Solution_reverseKGroup_25 {

    public static void main(String[] args) {

        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));

        ListNode listNode = reverseKGroup(head, 3);
        System.out.println(listNode);
    }

    /**
     * eg:
     * 1->2->3->4->5->6->7->8->null
     * 当k=3时
     * 1、割开：
     * 1->2->3
     * 4->5->6
     * 7->8->null  注：这里不够3个数，不需要反转，所以每次反转前需要计算链表长度
     * 2、对1中的链表数组一个个进行反转，按顺序尾首链接起来
     * 注意：凑不足k个数的链表，不需要反转
     *
     * @param head
     * @param k
     * @return
     */
    public static ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) {
            return head;
        }
        Map<Integer, ListNode> map = new TreeMap<>(Comparator.comparingInt(o -> o));
        int time = 1;
        int setValue = 0;
        ListNode next;
        while (head != null) {
            ListNode tmp = head;
            while (time++ < k) {
                if (tmp == null) {
                    break;
                }
                tmp = tmp.next;
            }
            if (tmp == null) {
                next = null;
            } else {
                next = tmp.next;
                tmp.next = null;

            }
            map.put(setValue++, head);
            head = next;
            time = 1;
        }
        // 反转链表
        for (Map.Entry<Integer, ListNode> mp : map.entrySet()) {
            int key = mp.getKey();
            head = mp.getValue();
            // 是否满足长度为k
            next = head;
            time = 0;
            ListNode pre = null;
            while (next != null) {
                time++;
                next = next.next;
            }
            if (time == k) {
                while (head != null) {
                    next = head.next;
                    head.next = pre;
                    pre = head;
                    head = next;
                }
            } else {
                pre = head;
            }
            map.put(key, pre);
        }
        ListNode ans = map.get(0);
        next = ans;
        for (Map.Entry<Integer, ListNode> mp : map.entrySet()) {
            System.out.println(mp.getKey());
            ListNode node = mp.getValue();
            if (node == ans) {
                continue;
            }
            while (next.next != null) {
                next = next.next;
            }
            next.next = node;
        }
        return ans;
    }


}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}